#include "levenshteinDistance.h"


double levenshteinDistanceCalculator::distance( const std::string& source, const std::string& target, const editOperationsCostHolderBase* _costHolder, bool allowTransposition )
{
	const int sourceLength = source.length();
	const int targetLength = target.length();

	const editOperationsCostHolderBase* costHolder;

	if( _costHolder == 0 ) {
		costHolder = defaultCostHolder.get();
	} else {
		costHolder = _costHolder;
	}

	std::vector<std::vector<double > > distanceMatrix( sourceLength + 1, std::vector<double>( targetLength + 1, 0.0 ) );
	initDistanceMatrix( distanceMatrix );

	for( size_t sourceCharacterIndex = 1; sourceCharacterIndex < distanceMatrix.size(); ++ sourceCharacterIndex ) {
		for( size_t targetCharacterIndex = 1; targetCharacterIndex < distanceMatrix[0].size(); ++targetCharacterIndex ) {
			const double deletionCost = distanceMatrix[sourceCharacterIndex - 1][targetCharacterIndex] +
				costHolder->deletionCost( source[sourceCharacterIndex - 1], target[ targetCharacterIndex - 1 ] );

			const double insertionCost = distanceMatrix[sourceCharacterIndex][targetCharacterIndex - 1] +
				costHolder->insertionCost( source[sourceCharacterIndex - 1], target[ targetCharacterIndex - 1 ] );

			const double substitutionCost = distanceMatrix[sourceCharacterIndex - 1][targetCharacterIndex - 1] +
				costHolder->substitutionCost( source[sourceCharacterIndex - 1], target[ targetCharacterIndex - 1 ] );

			distanceMatrix[sourceCharacterIndex][targetCharacterIndex] = std::min( std::min( deletionCost, insertionCost ), substitutionCost );
			if( allowTransposition ) {
				if( sourceCharacterIndex > 1 && targetCharacterIndex > 1
					&& source[sourceCharacterIndex - 1] == target[ targetCharacterIndex - 2 ]
				&& source[sourceCharacterIndex - 2] == target[ targetCharacterIndex - 1 ] )
				{
					distanceMatrix[sourceCharacterIndex][targetCharacterIndex] = std::min(
						distanceMatrix[sourceCharacterIndex][targetCharacterIndex],
						distanceMatrix[sourceCharacterIndex - 2][targetCharacterIndex - 2] + costHolder->transpositionCost( source[sourceCharacterIndex - 1], 
						target[ targetCharacterIndex - 1 ] )
					);
				}
			}
		}
	}
	return distanceMatrix.back().back();
}


void levenshteinDistanceCalculator::initDistanceMatrix( std::vector<std::vector<double > >& distanceMatrix )
{
	for( size_t firstColumnIndex = 0; firstColumnIndex < distanceMatrix.size(); ++firstColumnIndex ) {
		distanceMatrix[firstColumnIndex][0] = firstColumnIndex;
	}
	for( size_t firstRowIndex = 0; firstRowIndex < distanceMatrix[0].size(); ++firstRowIndex ) {
		distanceMatrix[0][firstRowIndex] = firstRowIndex;
	}
}
